Since a storage medium is subject to various types of noise, distortion and interference, various errors can occur at the output of the storage medium. The massive amount of digital data stored in an optical disk storage increases the probability of the errors. To correct the errors, error control coding is used. Reference is now made to FIG. 1, wherein an error correction system comprises an encoder 22, which transforms an input information sequence entered on the optical disk storage into code words.
In optical disk applications the code words are encoded based on International Standard Organization (ISO) Standard that requires Cyclic Redundancy Check (CRC) encoding and incorporates a Reed-Solomon (RS) code over some Galois fields. The RS (n,k) code is a cyclic symbol error-correcting code where k symbols of an original data are encoded. The result, which is an (n-k)-symbol redundancy block, is appended to the data.
The Galois field is a finite field, the elements of which may be represented as polynomials with a particular primitive element as variables. The RS code represents a block sequence of a Galois field GF(2.sup.m) of 2.sup.m binary symbols, where m is the number of bits per symbol. Constructing the Galois field GF(2.sup.m) requires a generator polynomial p(x) of degree m and a primitive element .beta., which is a root of p(x). The powers of .beta. generate all nonzero elements of GF(2.sup.m). Encoding and decoding circuitry is therefore required which has a capability of performing Galois field arithmetic.
The encoder 22 generates, in k steps, (n-k) redundancy bytes, which are appended to the original code data to make a n-byte code word. A writing unit 24 records the coded data on an optical disk 26.
A reading unit 28 unloads data from the optical disk 26 and transfers them to a decoding section 30. The decoding section 30 comprises a syndrome generator 32, which detects errors and generates syndrome bytes S(x) for each word received from the optical disk. The syndrome (n-k) bytes are supplied to an Euclidean operation circuit 34, which finds an error location polynomial .alpha.(x) and error value polynomial .eta.(x) using an extended Euclidean algorithm. The Euclidean operation circuit 34 is connected to an error locating circuit 36, which uses the Chien Search process to find actual error locations based on the error location polynomial .sigma.(x). The error locations together with the error value polynomial .eta.(x) and error location polynomial .sigma.(x) are used by an error value calculator 38 to determine error value at each error location found by the Chien Search process. An error correcting circuit 40 uses known error locations and values to correct the errors. Thus, the error locating circuit determines the location of the errors within each word using the Chien Search process. This search tests each possible error position suggested by the error location polynomial .sigma.(x) to establish the error location.
For error correction circuitry capable of correcting a maximum of 8 bytes for every 120 byte code word, used in an optical disk storage, a shortened RS (120, 104) code over the Galois field GF(2.sup.8) is required. This field consists of 256 vectors which represent every number between and including 0 to 255. These vectors are referenced using a specific element .alpha..sup.i, where i=0, 1, . . . , 255. In order to generate GF(2.sup.8), a generator polynomial p(x) of degree 8 and a primitive element .beta..sup.j are required. The primitive element .beta..sup.j can be used to generate another field by the same polynomial. The j represents a number coprime to 2.sup.m -1 for GF(2.sup.m), i.e. a number which is not divisible by 2.sup.m -1 or any of its factors. For GF(2.sup.8), there are 128 different primitive elements .beta..sup.j, which can be used to generate various fields from each particular generator polynomial.
Therefore, for locating errors, the error location polynomial of degree 8 is used EQU .alpha.(x)=r.sub.0 +r.sub.1 .multidot.x+r.sub.2 .multidot.x.sup.2 +. . . +r.sub.8 .multidot.x.sup.8 ( 1)
where r.sub.0 -r.sub.8 are the coefficients of the location polynomial determined by the Euclidean operation circuit 34, and x=.alpha..sup.i. The variable i is dependent upon the number of bytes per word (possible error locations) and the size of the Galois field. A set of unary multipliers and registers is used to check consecutively each byte in the codeword for a possible error location. Each of the unary multipliers consists of a plurality of Exclusive-OR. (XOR) gates. The number of the XOR gates is directly related to the number of test patterns required to acquire a reasonable fault coverage. Reduction of the number of test patterns would allow the error locating circuit to decrease the testing tine. This decrease would cause the processing speed of the error correction system to be increased. Also, reduction of the number of the XOR gates would allow the area of an error correction chip occupied by an error locating circuit to be decreased. Moreover, these unary multipliers which consist of a plurality of XOR gates are used in a plurality of modules in an error correction system. By applying the set of XORs, which is already implemented in another portion of the chip, the regularity of the IC design process would be improved.
In view of the above, it would be desirable to provide a circuit for locating errors in optical disks, wherein the fewest number of the XOR gates could be used. It would also be desirable to provide a circuit for locating errors in optical disks, which uses the same set of XORs as another module the error correction system.